來來來，各位看官今天是insertion sort囉～
在Selection Sort的部分我們已經講解使用selection sort會如何去對一串未排序的數列作排序的動作，那今天就要來介紹另外一個基本的sort

insertion sort 笑屁 (歐飛

在此復習一下selection sort，selection sort的方式是去選擇最大or最小值，然後加入已排序的集合最後面,也就表示，一開始就必須要從未排序集合中去尋找最小值or最大值的動作，也就是先做compare後，就可直接加入已排序最後面

而insertion sort不同的地方在於，每次選擇未排序集合最前端的值，然後加入已排序集合中適當的位置，而所謂的適當的位置，也就是需要去做compare的動作，也就是說，先直接選擇未排序中最前面的值，再去做compare的動作，放入已排序的集合中(如下圖顯示兩者之不同)

在瞭解insertion sort的做法後，就來試試看用Javascript實作出來吧
在此先依照由大到小排序
好的，首先呢當然是先寫出第一個function，將陣列值取出來方便後續處理

function insertionSort(list) {
for(var i = 0; i < list.length; i++) {
   //在此就可以將陣列list及每一個值丟進另外一個處理compare的function作處理

}

接下來是在已排序的集合中，去找出適當的位置來插入，而適當的位置應該就是找出已排序集合中是否有值比自己小(就代表自己比較大應該排在他前面)，如果有，就必須要做插入的動作，如果沒有，就可以不需要動

//return i表示為比自己小到list的哪一個位置
//如果沒有比自己小的，就會跑到i = elementIdx，那return的就是自己的位置
function insertedIdx(list, elementIdx) {
//搜尋已排序集合
for(var i = 0; i < elementIdx; i++) {
    if(list[i] < list[elementIdx]) { break; }
}
return i;
}

找到i後，就可以開始做插入的動作，而原本是要做出插入至比自己小的數值前面，也就是說，先將原本在那位置及在它後面的元素往後退一位後,空出來的位置，就是是把自己插入的位置了

function insert(list,elementIdx ,insertedIdx){
    var tmp = list[elementIdx];

    for(var i = elementIdx; i > inserted; i--)
    {
        list[i] = list[i-1];

    } 
   list[insertedIdx] = tmp; 

}

大公告成><，在把寫完的function在第一個function中完成呼叫動作即可～

function insertionSort(list) {
for(var i = 0; i < list.length; i++) {
    var inserted = insertedIdx(list, i);

    if(inserted !== i) { insert(list, i, inserted); }
 }    
}

以下是完整的程式碼～請參考之~~

//尋找要插入的位置
function insertedIdx(list, elementIdx) {
//搜尋已排序集合
for(var i = 0; i < elementIdx; i++) {
    if(list[i] < list[elementIdx]) { break; }
}
return i;
}
//插入至
function insert(list, elementIdx, inserted) {
    var tmp = list[elementIdx];

    for(var i = elementIdx; i > inserted; i--)
    {
        list[i] = list[i-1];

    }  
list[inserted] = tmp;
console.log(list[inserted]);
}

function insertionSort(list) {
    for(var i = 0; i < list.length; i++) {
        var inserted = insertedIdx(list, i);
        //如果不是原本那位置的話，代表需要做插入動作
    if(inserted !== i) { insert(list, i, inserted); }
    }    
}
var list = [10, 9, 1, 2, 5, 3, 8, 7];
insertionSort(list);
alert(list);

可執行的jsfiddle在此～
http://jsfiddle.net/stanney/UsTee/1/

下一個就是可愛的小賴大大喜歡的可愛的bubble sort囉～